//滑动窗口最大值
class Solution {
public:
    //实现一个自定义双端队列 只存入后续有可能成为最大值的值
    //比如 5 4 2 1 0 当5脱离k个数字的范围 4 就成为了最大值
    //所以这个队列的队头元素是队列中的最大值
    //该队列pop元素时 只有该删除的元素==队里最大元素时 才真的将队头元素pop掉
    class myq
    {
    public:
        void pushV(int val)
        {
            while(!q.empty() && val>q.back())
            {
                q.pop_back();
            }
            q.push_back(val);
        }  
        void popV(int val)
        {
            if(!q.empty() && q.front()==val)
            {
                q.pop_front();
            }
        }
        int getmax()
        {
            return q.front();
        }
    private:
        deque<int> q;
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        vector<int>res;
        myq q;
        for(int i=0;i<k;i++)
        {
            q.pushV(nums[i]);
        }
        res.push_back(q.getmax());
        for(int i=k;i<nums.size();i++)
        {
            q.popV(nums[i-k]);
            q.pushV(nums[i]);
            res.push_back(q.getmax());
        }
        return res;
    }
};
//前K个高频元素
class Solution {
public:
    struct cmp
    {
        bool operator()(const pair<int,int>& p1,const pair<int,int>& p2 )
        {
            return p1.second>p2.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        //首先需要一个结构 既存入元素 又存入出现次数
        unordered_map<int,int>hash;
        for(int i=0;i<nums.size();i++)
        {
            hash[nums[i]]++;
        }
        //存好了 现在利用优先级队列进行排序
        //unordered_map中的结构是pair 针对pair 做一个仿函数
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
        // for(int i=0;i<nums.size();i++)
        // {
        //     q.push(nums[i]);
        //     if(q.size()>k) q.pop();
        // } nums里面有重复值
        for(auto it=hash.begin();it!=hash.end();it++)
        {
            //q存的是pair
            q.push(*it);
            if(q.size()>k) q.pop();
        }
        vector<int>res(k);
        for(int i=k-1;i>=0;i--)
        {
            res[i]=q.top().first;
            q.pop();
        }
        return res;
    }
};
//二叉树最小深度
class Solution {
public:
    int minDepth(TreeNode* root) 
    {
        if(!root) return 0;
        int left=minDepth(root->left);
        int right=minDepth(root->right);
        //为什么要加下面的判断呢？
        if(!root->left && !root->right)
        {
            return 1;
        }
        if(!root->left && root->right)
        {
            return 1+right;
        }
        if(root->left && ! root->right)
        {
            return 1+left;
        }
        //因为如果没有上述判断 如果根节点没有左树或右树的其中一个 就会直接返回1+0
        //而题目中最小深度是指：从根节点到最近叶子节点的最短路径上的节点数量
        return 1+min(left,right);
    }
};
//最大深度
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        if(!root) return 0;
        int left=maxDepth(root->left);
        int right=maxDepth(root->right);
        return max(left,right)+1;
    }
};
//对称二叉树
class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        if(!root) return true;
        return func(root->left,root->right);
    }
    bool func(TreeNode* p1, TreeNode* p2)
    {
        if(!p1 && !p2) return true;
        else if( (!p1 && p2)  || (p1 && !p2)) return false;
        else if(p1->val !=p2->val ) return false;
        return func(p1->left,p2->right) && func(p1->right,p2->left);
    }
};